package com.zhugang.week04;

/**
 * @program algorithms
 * @description: findKthLargest
 * @author: chanzhugang
 * @create: 2022/06/17 17:25
 */
public class FindKthLargest {

    public static void main(String[] args) {
        FindKthLargest findKthLargest = new FindKthLargest();
        int[] nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int res = findKthLargest.findKthLargest(nums, 4);
        System.out.println(res);
    }

    /**
     * 215. 数组中的第k个最大元素
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        /**
         * 快排找分区点,分区点满足条件即是第K大元素
         */
        return quickSort_r(nums, 0, nums.length - 1, k);
    }

    private int quickSort_r(int[] nums, int p, int r, int k) {
        if (p > r) {
            return -1;
        }
        int q = partition(nums, p, r);
        if (q - p + 1 == k) {
            return nums[q];
        } else if (q - p + 1 < k) {
            // 右边
            return quickSort_r(nums, q + 1, r, k - (q - p + 1));
        } else {
            return quickSort_r(nums, p, q - 1, k);
        }
    }

    private int partition(int[] nums, int p, int r) {
        // 倒序：找分区点位置，大的放左边，小的放右边； 双指针法(不推荐)
        int i = p;
        int j = r - 1;
        while (i < j) {
            if (nums[i] > nums[r]) {
                i++;
                continue;
            }
            if (nums[j] <= nums[r]) {
                j--;
                continue;
            }
            swap(nums, i, j);
            i++;
            j--;
           /* while (i < j && nums[i] > nums[r]) {
                // nums[i]大 ++
                i++;
            }
            while (i < j && nums[j] <= nums[r]) {
                // nums[j]小 --
                j--;
            }
            if (i < j) {
                // nums[i] < privot;   nums[j] 大于privot
                swap(nums, i, j);
                i++;
                j--;
            }*/
        }
        if (j >= p && nums[j] < nums[r]) {
            swap(nums, j, r);
            return j;
        } else {
            swap(nums, j + 1, r);
            return j + 1;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}